/**
 * @author : xwj
 * @date : 2021/9/12 21:46
 * @description : 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * @class : test19
 **/



public class test19 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //1. 0 ms	36.2 MB
    //先计算出链表的长度，在删除对应位置节点
    //初始化一个头结点用于存放head, 避免head只有一个元素时， 被删除了，找不到头结点
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        int length = 0;
        ListNode r = head;
        while (r != null) {
            length++;
            r = r.next;
        }
        r = new ListNode(0, head);
        ListNode re = r;
        for (int i = 1; i < length - n +1; ++i) {
            re = re.next;
        }
        re.next = re.next.next;
        return r.next;
    }

    public static void main(String[] args) {
        int n = 1;
        ListNode tail = new ListNode(5);
        ListNode l1 = new ListNode(4, tail);
        ListNode l2 = new ListNode(3, l1);
        ListNode l3 = new ListNode(2, l2);
        ListNode head = new ListNode(1, l3);
        ListNode r = removeNthFromEnd1(head, n);

        while (r != null) {
            System.out.print(r.val + " ");
            r = r.next;
        }
    }

}
